<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-10.html">previous</a></span><span>, <a href="book-Z-H-12.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_sec_1.2"></a>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_1.2">1.2&nbsp;&nbsp;Procedures and the Processes They Generate</a></h2><p>

<p>


We have now considered the elements of programming: We have used
primitive arithmetic operations, we have combined these operations, and
we have abstracted these composite operations by defining them as compound
procedures.  But that is not enough to enable us to say that we know
how to program.  Our situation is analogous to that of someone who has
learned the rules for how the pieces move in chess but knows nothing
of typical openings, tactics, or strategy.  Like the novice chess
player, we don't yet know the common patterns of usage in the domain.
We lack the knowledge of <span class="note-red">which moves are worth making (which
procedures are worth defining)</span>.  We lack the experience to <span class="note-red">predict the
consequences of making a move (executing a procedure)</span>.<p>

<span class="note-red">The ability to visualize the consequences of the actions under
consideration is crucial to becoming an expert programmer</span>, just as it
is in any synthetic, creative activity.  In becoming an expert
photographer, for example, one must learn how to look at a scene and
know how dark each region will appear on a print for each possible
choice of exposure and development conditions.  Only then can one
reason backward, planning framing, lighting, exposure, and development
to obtain the desired effects.  So it is with programming, where we
are planning the course of action to be taken by a process and where
we control the process by means of a program.  To become experts, we
must learn to visualize the processes generated by various types of
procedures.  Only after we have developed such a skill can we learn
to reliably construct programs that exhibit the desired behavior.<p>

<a name="%_idx_630"></a><a name="%_idx_632"></a><a name="%_idx_634"></a>A procedure is a pattern for the <em>local evolution</em> of a
computational process.  It specifies how each stage of the process is
built upon the previous stage.  We would like to be able to make
statements about the overall, or <em>global</em>, behavior of a
process whose local evolution has been specified by a procedure.  This
is very difficult to do in general, but we can at least try to
describe some typical patterns of process evolution.<p>

In this section we will examine some common ``shapes'' for processes
generated by simple procedures.  We will also investigate the
rates at which these processes consume the important computational
resources of time and space.  The procedures we will consider
are very simple.  Their role is like that played by test patterns in
photography: as oversimplified prototypical patterns, rather than
practical examples in their own right.<p>

<a name="%_sec_1.2.1"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.2.1">1.2.1&nbsp;&nbsp;Linear Recursion and Iteration</a></h3><p>


<a name="%_idx_636"></a><a name="%_idx_638"></a>
<a name="%_fig_1.3"></a><p><div align=left><table width=100%><tr><td><img src="ch1-Z-G-7.gif" border="0">
</td></tr><caption align=bottom><div align=left><b>Figure 1.3:</b>&nbsp;&nbsp;A linear recursive process for computing 6!.</div></caption><tr><td>

</td></tr></table></div><p><p>

<a name="%_idx_640"></a>We begin by considering the factorial function, defined by<p>

<p><div align=left><img src="ch1-Z-G-8.gif" border="0"></div><p><p>

There are many ways to compute factorials.  One way is to make use of
the observation that <em>n</em>! is equal to <em>n</em> times (<em>n</em> - 1)! for
any positive integer&nbsp;<em>n</em>:<p>

<p><div align=left><img src="ch1-Z-G-9.gif" border="0"></div><p><p>

Thus, we can compute <em>n</em>! by computing (<em>n</em> - 1)! and multiplying the
result by <em>n</em>.  If we add the stipulation that 1! is equal to 1,
this observation translates directly into a procedure:<p>

<p><p><tt><a name="%_idx_642"></a>(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;n&nbsp;(factorial&nbsp;(-&nbsp;n&nbsp;1)))))<br>
</tt><p><p>
<a name="%_idx_644"></a>We can use the substitution model of
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a> to watch this procedure in action
computing 6!, as shown in figure&nbsp;<a href="#%_fig_1.3">1.3</a>.<p>


Now let's take a different perspective on computing factorials.  We
could describe a rule for computing <em>n</em>! by specifying that we
first multiply 1 by 2, then multiply the result by 3, then by 4,
and so on until we reach <em>n</em>.
More formally, we maintain a running product, together with a counter
that counts from 1 up to <em>n</em>.  We can describe the computation by
saying that the counter and the product simultaneously change from one
step to the next according to the rule<p>

<p><p>product  <img src="book-Z-G-D-14.gif" border="0">  counter  &middot;  product <p>

<p><p>counter  <img src="book-Z-G-D-14.gif" border="0">  counter  +  1<p>

<p><p><p>

and stipulating that <em>n</em>! is the value of the product when
the counter exceeds <em>n</em>.<p>

<a name="%_fig_1.4"></a><p><div align=left><table width=100%><tr><td><img src="ch1-Z-G-10.gif" border="0">
</td></tr><caption align=bottom><div align=left><b>Figure 1.4:</b>&nbsp;&nbsp;A linear iterative process for computing 6!.</div></caption><tr><td> 

</td></tr></table></div><p><p>

Once again, we can recast our description as a procedure for computing
factorials:<a name="call_footnote_Temp_46" href="#footnote_Temp_46"><sup><small>29</small></sup></a><p>

<p><p><tt><a name="%_idx_646"></a>(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;(fact-iter&nbsp;1&nbsp;1&nbsp;n))<br>
<br>
(define&nbsp;(fact-iter&nbsp;product&nbsp;counter&nbsp;max-count)<br>
&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;counter&nbsp;max-count)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;product<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fact-iter&nbsp;(*&nbsp;counter&nbsp;product)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;counter&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max-count)))<br>
</tt><p><p><p>


As before, we can use the substitution model to visualize the process
of computing 6!, as shown in figure&nbsp;<a href="#%_fig_1.4">1.4</a>.<p>

Compare the two processes.  From one point of view, they seem hardly
different at all.  Both compute the same mathematical function on the
same domain, and each requires a number of steps proportional to <em>n</em>
to compute <em>n</em>!.  Indeed, both processes even carry out the same
sequence of multiplications, obtaining the same sequence of partial
products.  On the other hand, when we consider the <a name="%_idx_648"></a><a name="%_idx_650"></a>``shapes'' of the
two processes, we find that they evolve quite differently.<p>

Consider the first process.  The substitution model reveals a shape of
expansion followed by contraction, indicated by the arrow in
figure&nbsp;<a href="#%_fig_1.3">1.3</a>.  The expansion occurs as the
process builds up a chain of <a name="%_idx_652"></a><em>deferred operations</em> (in this case,
a chain of multiplications).  The contraction occurs as 
the operations are
actually performed.  This type of process, characterized by a chain of
deferred operations, is called a <a name="%_idx_654"></a><a name="%_idx_656"></a><em>recursive process</em>.  Carrying
out this process requires that the interpreter keep track of the
operations to be performed later on.  In the computation of <em>n</em>!,
the length of the chain of deferred multiplications, and hence the amount
of information needed to keep track of it, <a name="%_idx_658"></a>grows linearly with <em>n</em>
(is proportional to <em>n</em>), just like the number of steps.
<a name="%_idx_660"></a><a name="%_idx_662"></a><a name="%_idx_664"></a>Such a process is called a <em>linear recursive process</em>.<p>

By contrast, the second process does not grow and shrink.  At each
step, all we need to keep track of, for any <em>n</em>, are the current
values of the variables <tt>product</tt>, <tt>counter</tt>, and <tt>max-count</tt>.  We call this an <a name="%_idx_666"></a><a name="%_idx_668"></a><em>iterative process</em>.  In general, an
iterative process is one whose state can be summarized by a fixed
number of <a name="%_idx_670"></a><em>state variables</em>, together with a fixed rule that
describes how the state variables should be updated as the process
moves from state to state and an (optional) end test that specifies
conditions under which the process should terminate.  In computing
<em>n</em>!, the number of steps required grows linearly with <em>n</em>.  Such a process is
called a <a name="%_idx_672"></a><a name="%_idx_674"></a><a name="%_idx_676"></a><em>linear iterative process</em>.<p>

The contrast between the two processes can be seen in another way.  In
the iterative case, the program variables provide a complete
description of the state of the process at any point.  If we stopped
the computation between steps, all we would need to do to resume the
computation is to supply the interpreter with the values of the three
program variables.  Not so with the recursive process.  In this case
there is some additional ``hidden'' information, maintained by the
interpreter and not contained in the program variables, which
indicates ``where the process is'' in negotiating the chain of
deferred operations.  The longer the chain, the more information must
be maintained.<a name="call_footnote_Temp_47" href="#footnote_Temp_47"><sup><small>30</small></sup></a><p>

In contrasting iteration and recursion, we must be careful not to
confuse the notion of a <a name="%_idx_680"></a><a name="%_idx_682"></a>recursive <em>process</em> with the notion of a
recursive <em>procedure</em>.  When we describe a procedure as recursive,
we are referring to the syntactic fact that the procedure definition
refers (either directly or indirectly) to the procedure itself.  But
when we describe a process as following a pattern that is, say,
linearly recursive, we are speaking about how the process evolves, not
about the syntax of how a procedure is written.  It may seem
disturbing that we refer to a recursive procedure such as <tt>fact-iter</tt> as generating an iterative process.  However, the process
really is iterative: Its state is captured completely by its three
state variables, and an interpreter need keep track of only three
variables in order to execute the process.<p>

One reason that the distinction between process and procedure may be
confusing is that most implementations of common languages (including
<a name="%_idx_684"></a><a name="%_idx_686"></a><a name="%_idx_688"></a>Ada, Pascal, and C) are designed in such a way that the
interpretation of any recursive procedure consumes an amount of memory
that grows with the number of procedure calls, even when the process
described is, in principle, iterative.  As a consequence, these
languages can describe iterative processes only by resorting to
special-purpose <a name="%_idx_690"></a>``looping constructs'' such as <tt>do</tt>, <tt>repeat</tt>,
<tt>until</tt>, <tt>for</tt>, and <tt>while</tt>.  The implementation of Scheme
we shall consider in chapter&nbsp;5 does not share this defect.  <span class="note-red">It will
execute an iterative process in constant space, even if the iterative
process is described by a recursive procedure.</span>  An implementation with
this property is called <a name="%_idx_692"></a><em>tail-recursive</em>.  With a tail-recursive
implementation, <a name="%_idx_694"></a>iteration can be expressed using the ordinary
procedure call mechanism, so that special iteration constructs are
useful only as <a name="%_idx_696"></a>syntactic sugar.<a name="call_footnote_Temp_48" href="#footnote_Temp_48"><sup><small>31</small></sup></a><p>

<p><a name="%_thm_1.9"></a>
<b>Exercise 1.9.</b>&nbsp;&nbsp;Each of the following two procedures defines a method for adding two
positive integers in terms of the procedures <tt>inc</tt>,
which increments its argument by 1, and <tt>dec</tt>, which decrements
its argument by 1.<p>

<p><p><tt>(define&nbsp;(+&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;a&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(inc&nbsp;(+&nbsp;(dec&nbsp;a)&nbsp;b))))<br>
<br>
(define&nbsp;(+&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;a&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(dec&nbsp;a)&nbsp;(inc&nbsp;b))))<br>
</tt><p><p>
Using the substitution model, illustrate the process generated by each
procedure in evaluating <tt>(+ 4 5)</tt>.  Are these processes
iterative or recursive?
<p><p>

<p><a name="%_thm_1.10"></a>
<b>Exercise 1.10.</b>&nbsp;&nbsp;<a name="%_idx_708"></a><a name="%_idx_710"></a>The following procedure computes a mathematical function called
Ackermann's function.<p>

<p><p><tt>(define&nbsp;(A&nbsp;x&nbsp;y)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;y&nbsp;0)&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;x&nbsp;0)&nbsp;(*&nbsp;2&nbsp;y))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;y&nbsp;1)&nbsp;2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(A&nbsp;(-&nbsp;x&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(A&nbsp;x&nbsp;(-&nbsp;y&nbsp;1))))))<br>
</tt><p><p>
What are the values of the following expressions?<p>

<p><p><tt>(A&nbsp;1&nbsp;10)<br>
<br>
(A&nbsp;2&nbsp;4)<br>
<br>
(A&nbsp;3&nbsp;3)<br>
</tt><p><p>
Consider the following procedures, where <tt>A</tt> is the procedure  
defined above:
<p><p><tt>(define&nbsp;(f&nbsp;n)&nbsp;(A&nbsp;0&nbsp;n))<br>
<br>
(define&nbsp;(g&nbsp;n)&nbsp;(A&nbsp;1&nbsp;n))<br>
<br>
(define&nbsp;(h&nbsp;n)&nbsp;(A&nbsp;2&nbsp;n))<br>
<br>
(define&nbsp;(k&nbsp;n)&nbsp;(*&nbsp;5&nbsp;n&nbsp;n))<br>
</tt><p><p>
Give concise mathematical definitions for the functions computed by
the procedures <tt>f</tt>, <tt>g</tt>, and <tt>h</tt> for positive integer
values of <em>n</em>.  For example, <tt>(k n)</tt> computes 5<em>n</em><sup>2</sup>.
<p><p>

<a name="%_sec_1.2.2"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.2.2">1.2.2&nbsp;&nbsp;Tree Recursion</a></h3><p>


<a name="%_idx_712"></a><a name="%_idx_714"></a><a name="%_idx_716"></a>
Another common pattern of computation is called <em>tree recursion</em>.
As an example, consider computing the sequence of <a name="%_idx_718"></a>Fibonacci numbers,
in which each number is the sum of the preceding two:<p>

<p><div align=left><img src="ch1-Z-G-11.gif" border="0"></div><p><p>

In general, the Fibonacci numbers can be defined by the rule
<p><div align=left><img src="ch1-Z-G-12.gif" border="0"></div><p>
We can immediately translate this definition into a recursive
procedure for computing Fibonacci numbers:<p>

<p><p><tt><a name="%_idx_720"></a>(define&nbsp;(fib&nbsp;n)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;n&nbsp;0)&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;n&nbsp;1)&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(+&nbsp;(fib&nbsp;(-&nbsp;n&nbsp;1))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fib&nbsp;(-&nbsp;n&nbsp;2))))))<br>
</tt><p><p><p>

<a name="%_fig_1.5"></a><p><div align=left><table width=100%><tr><td><img src="ch1-Z-G-13.gif" border="0">
</td></tr><caption align=bottom><div align=left><b>Figure 1.5:</b>&nbsp;&nbsp;The tree-recursive process generated in computing <tt>(fib 5)</tt>.</div></caption><tr><td>

</td></tr></table></div><p><p>

Consider the pattern of this computation.  To compute <tt>(fib 5)</tt>,
we compute <tt>(fib 4)</tt> and <tt>(fib 3)</tt>.  To compute <tt>(fib 4)</tt>,
we compute <tt>(fib 3)</tt> and <tt>(fib 2)</tt>.  In general, the evolved
process looks like a tree, as shown in figure&nbsp;<a href="#%_fig_1.5">1.5</a>.
Notice that the branches split into two at each level (except at the
bottom); this reflects the fact that the <tt>fib</tt> procedure calls
itself twice each time it is invoked.<p>


This procedure is instructive as a prototypical tree recursion, but it
is a terrible way to compute Fibonacci numbers because it does so much
redundant computation.  Notice in figure&nbsp;<a href="#%_fig_1.5">1.5</a> that
the entire computation of <tt>(fib 3)</tt> -- almost half the work -- is
duplicated.  In fact, it is not hard to show that the number of times
the procedure will compute <tt>(fib 1)</tt> or <tt>(fib 0)</tt> (the number
of leaves in the above tree, in general) is precisely 
<em>F</em><em>i</em><em>b</em>(<em>n</em> + 1).  To get an idea of how bad this is, one can show that the
value of  <em>F</em><em>i</em><em>b</em>(<em>n</em>) <a name="%_idx_722"></a>grows exponentially with <em>n</em>.  More precisely
(see exercise&nbsp;<a href="#%_thm_1.13">1.13</a>),  <em>F</em><em>i</em><em>b</em>(<em>n</em>) is the closest
integer to <img src="book-Z-G-D-11.gif" border="0"><sup><em>n</em></sup> /<img src="book-Z-G-D-13.gif" border="0">5, where<p>

<p><div align=left><img src="ch1-Z-G-14.gif" border="0"></div><p>
is the <a name="%_idx_724"></a><em>golden ratio</em>, which satisfies the equation<p>

<p><div align=left><img src="ch1-Z-G-15.gif" border="0"></div><p>

Thus, the process uses a number of steps that grows exponentially
with the input.  On the other hand, the space required grows only
linearly with the input, because we need keep track only of which
nodes are above us in the tree at any point in the computation.  In
general, the number of steps required by a tree-recursive process will be
proportional to the number of nodes in the tree, while the space
required will be proportional to the maximum depth of the tree.<p>

We can also formulate an iterative process for computing the
Fibonacci numbers.  The idea is to use a pair of integers <em>a</em> and
<em>b</em>, initialized to  <em>F</em><em>i</em><em>b</em>(1) = 1 and  <em>F</em><em>i</em><em>b</em>(0) = 0,
and to repeatedly apply the simultaneous
transformations
<p><div align=left><img src="ch1-Z-G-16.gif" border="0"></div><p>
It is not hard to show that, after applying this transformation <em>n</em>
times, <em>a</em> and <em>b</em> will be equal, respectively, to  <em>F</em><em>i</em><em>b</em>(<em>n</em> + 1) and
 <em>F</em><em>i</em><em>b</em>(<em>n</em>).  Thus, we can compute Fibonacci numbers iteratively using
the procedure<p>

<p><p><tt><a name="%_idx_726"></a>(define&nbsp;(fib&nbsp;n)<br>
&nbsp;&nbsp;(fib-iter&nbsp;1&nbsp;0&nbsp;n))<br>
<br>
(define&nbsp;(fib-iter&nbsp;a&nbsp;b&nbsp;count)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;count&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fib-iter&nbsp;(+&nbsp;a&nbsp;b)&nbsp;a&nbsp;(-&nbsp;count&nbsp;1))))<br>
</tt><p><p>
This second method for computing  <em>F</em><em>i</em><em>b</em>(<em>n</em>) is a linear iteration.  The
difference in number of steps required by the two methods -- one linear in <em>n</em>,
one growing as fast as  <em>F</em><em>i</em><em>b</em>(<em>n</em>) itself -- is enormous, even for
small inputs.<p>

One should not conclude from this that tree-recursive processes are
useless.  When we consider processes that operate on hierarchically
structured data rather than numbers, we will find that tree recursion
is a natural and powerful tool.<a name="call_footnote_Temp_51" href="#footnote_Temp_51"><sup><small>32</small></sup></a> But even in numerical operations,
tree-recursive processes can be useful in helping us to understand and
design programs.  For instance, although the first <tt>fib</tt> procedure
is much less efficient than the second one, it is more
straightforward, being little more than a translation into Lisp of the
definition of the Fibonacci sequence.  To formulate the iterative
algorithm required noticing that the computation could be recast as an
iteration with three state variables.<p>

<a name="%_sec_Temp_52"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_52">Example: Counting change</a></h4><p>

<a name="%_idx_728"></a>
It takes only a bit of cleverness to come up with the iterative
Fibonacci algorithm.  In contrast, consider the
following problem: How many different ways can we make change of $ 1.00,
given half-dollars, quarters, dimes, nickels, and pennies?  More
generally, can we write a procedure to compute the number of ways to
change any given amount of money?<p>

This problem has a simple solution as a recursive procedure.  Suppose
we think of the types of coins available as arranged in some order.
Then the following relation holds:<p>

<p><p>The number of ways to change amount <em>a</em> using <em>n</em> kinds of coins equals<p>

<p><ul>
<li>the number of ways to change amount <em>a</em> using all but the first
kind of coin, plus<p>

<li>the number of ways to change amount <em>a</em> - <em>d</em> using all <em>n</em> kinds of
coins, where <em>d</em> is the denomination of the first kind of coin.
</ul><p><p>

To see why this is true, observe that the ways to make change can be
divided into two groups: those that do not use any of the first kind
of coin, and those that do.  Therefore, the total number of ways to
make change for some amount is equal to the number of ways to make
change for the amount without using any of the first kind of coin,
plus the number of ways to make change assuming that we do use the
first kind of coin.  But the latter number is equal to the number of
ways to make change for the amount that remains after using a coin of
the first kind.<p>

Thus, we can recursively reduce the problem of changing a given amount
to the problem of changing smaller amounts using fewer kinds of coins.
Consider this reduction rule carefully, and convince yourself that we
can use it to describe an algorithm if we specify the following
degenerate cases:<a name="call_footnote_Temp_53" href="#footnote_Temp_53"><sup><small>33</small></sup></a><p>

<p><ul>
<li>If <em>a</em> is exactly 0, we should count that as 1 way to make change.<p>

<li>If <em>a</em> is less than 0, we should count that as 0 ways to make change.<p>

<li>If <em>n</em> is 0, we should count that as 0 ways to make change.
</ul><p><p>

We can easily translate this description into a recursive
procedure:<p>

<p><p><tt><a name="%_idx_730"></a>(define&nbsp;(count-change&nbsp;amount)<br>
&nbsp;&nbsp;(cc&nbsp;amount&nbsp;5))<br>
(define&nbsp;(cc&nbsp;amount&nbsp;kinds-of-coins)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;amount&nbsp;0)&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((or&nbsp;(&lt;&nbsp;amount&nbsp;0)&nbsp;(=&nbsp;kinds-of-coins&nbsp;0))&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(+&nbsp;(cc&nbsp;amount<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;kinds-of-coins&nbsp;1))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cc&nbsp;(-&nbsp;amount<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(first-denomination&nbsp;kinds-of-coins))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;kinds-of-coins)))))<br>
(define&nbsp;(first-denomination&nbsp;kinds-of-coins)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;kinds-of-coins&nbsp;1)&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;kinds-of-coins&nbsp;2)&nbsp;5)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;kinds-of-coins&nbsp;3)&nbsp;10)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;kinds-of-coins&nbsp;4)&nbsp;25)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;kinds-of-coins&nbsp;5)&nbsp;50)))<br>
</tt><p><p>
(The <tt>first-denomination</tt> procedure takes as input the number of
kinds of coins available and returns the denomination of the first
kind.  Here we are thinking of the coins as arranged in order from
largest to smallest, but any order would do as well.)  We can now
answer our original question about changing a dollar:<p>

<p><p><tt>(count-change&nbsp;100)<br>
<i>292</i><br>
</tt><p><p><p>

<tt>Count-change</tt> generates a tree-recursive process with
redundancies similar to those in our first implementation of <tt>fib</tt>.  (It will take quite a while for that 292 to be computed.)  On
the other hand, it is not obvious how to design a better algorithm
for computing the result, and we leave this problem as a challenge.
The observation that a <a name="%_idx_732"></a>tree-recursive process may be highly
inefficient but often easy to specify and understand has led people to
propose that one could get the best of both worlds by designing a
``smart compiler'' that could transform tree-recursive procedures into
more efficient procedures that compute the same result.<a name="call_footnote_Temp_54" href="#footnote_Temp_54"><sup><small>34</small></sup></a><p>

<p><a name="%_thm_1.11"></a>
<b>Exercise 1.11.</b>&nbsp;&nbsp;A function <em>f</em> is defined by the rule that <em>f</em>(<em>n</em>) = <em>n</em> if <em>n</em>&lt;3 and
<em>f</em>(<em>n</em>) = <em>f</em>(<em>n</em> - 1) + 2<em>f</em>(<em>n</em> - 2) + 3<em>f</em>(<em>n</em> - 3) if <em>n</em><u>&gt;</u> 3.  Write a procedure that
computes <em>f</em> by means of a recursive process.  Write a procedure that
computes <em>f</em> by means of an iterative process.
<p><p>

<p><a name="%_thm_1.12"></a>
<b>Exercise 1.12.</b>&nbsp;&nbsp;<a name="%_idx_738"></a>The following pattern of numbers is called
<em>Pascal's triangle</em>.<p>

<p><div align=left><img src="ch1-Z-G-17.gif" border="0"></div><p>
The numbers at the edge of the triangle are all 1, and
each number inside the triangle is the sum of the two numbers above it.<a name="call_footnote_Temp_57" href="#footnote_Temp_57"><sup><small>35</small></sup></a>
Write a procedure that computes elements of Pascal's triangle by means
of a recursive process.
<p><p>

<p><a name="%_thm_1.13"></a>
<b>Exercise 1.13.</b>&nbsp;&nbsp;Prove that  <em>F</em><em>i</em><em>b</em>(<em>n</em>) is the closest integer to <img src="book-Z-G-D-11.gif" border="0"><sup><em>n</em></sup>/<img src="book-Z-G-D-13.gif" border="0">5,
where <img src="book-Z-G-D-11.gif" border="0"> =  (1 + <img src="book-Z-G-D-13.gif" border="0">5)/2.  Hint: Let <img src="book-Z-G-D-12.gif" border="0"> =  (1 - <img src="book-Z-G-D-13.gif" border="0">5)/2.  Use
induction and the definition of the Fibonacci numbers (see
section&nbsp;<a href="#%_sec_1.2.2">1.2.2</a>) to prove that  <em>F</em><em>i</em><em>b</em>(<em>n</em>) = (<img src="book-Z-G-D-11.gif" border="0"><sup><em>n</em></sup>
 - <img src="book-Z-G-D-12.gif" border="0"><sup><em>n</em></sup>)/<img src="book-Z-G-D-13.gif" border="0">5.

<p><p>

<a name="%_sec_1.2.3"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.2.3">1.2.3&nbsp;&nbsp;Orders of Growth</a></h3><p>


<a name="%_idx_752"></a>
The previous examples illustrate that processes can differ
considerably in the rates at which they consume computational
resources.  One convenient way to describe this difference is to use
the notion of <a name="%_idx_754"></a><em>order of growth</em> to obtain a gross measure of the
<a name="%_idx_756"></a>resources required by a process as the inputs become larger.<p>


Let <em>n</em> be a parameter that measures the size of the problem, and let
<em>R</em>(<em>n</em>) be the amount of resources the process requires for a problem
of size <em>n</em>.  In our previous examples we took <em>n</em> to be the number
for which a given function is to be computed, but there are other
possibilities.  For instance, if our goal is to compute an
approximation to the square root of a number, we might take <em>n</em> to be
the number of digits accuracy required.  For matrix multiplication we
might take <em>n</em> to be the number of rows in the matrices.  In general
there are a number of properties of the problem with respect to which
it will be desirable to analyze a given process.  Similarly, <em>R</em>(<em>n</em>)
might measure the number of internal storage registers used, the
number of elementary machine operations performed, and so on.  In
computers that do only a fixed number of operations at a time, the
time required will be proportional to the number of elementary machine
operations performed.<p>

<a name="%_idx_758"></a><a name="%_idx_760"></a>We say that <em>R</em>(<em>n</em>) has order of growth <img src="book-Z-G-D-3.gif" border="0">(<em>f</em>(<em>n</em>)), written
<em>R</em>(<em>n</em>) = <img src="book-Z-G-D-3.gif" border="0">(<em>f</em>(<em>n</em>)) (pronounced ``theta of <em>f</em>(<em>n</em>)''), if there are
positive constants <em>k</em><sub>1</sub> and <em>k</em><sub>2</sub> independent of <em>n</em> such that
<p><div align=left><img src="ch1-Z-G-18.gif" border="0"></div><p>
for any sufficiently large value of <em>n</em>.  (In other
words, for large <em>n</em>, the value <em>R</em>(<em>n</em>) is sandwiched between <em>k</em><sub>1</sub><em>f</em>(<em>n</em>)
and <em>k</em><sub>2</sub><em>f</em>(<em>n</em>).)<p>

<a name="%_idx_762"></a><a name="%_idx_764"></a><a name="%_idx_766"></a>For instance, with the linear recursive process for computing
factorial described in section&nbsp;<a href="#%_sec_1.2.1">1.2.1</a> the
number of steps grows proportionally to the input <em>n</em>.  Thus, the
steps required for this process grows as <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>).  We also saw
that the space required grows as <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>).  For the <a name="%_idx_768"></a><a name="%_idx_770"></a><a name="%_idx_772"></a>iterative
factorial, the number of steps is still <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>) but the space is
<img src="book-Z-G-D-3.gif" border="0">(1) -- that is, constant.<a name="call_footnote_Temp_59" href="#footnote_Temp_59"><sup><small>36</small></sup></a> The <a name="%_idx_774"></a><a name="%_idx_776"></a><a name="%_idx_778"></a>tree-recursive Fibonacci computation requires
<img src="book-Z-G-D-3.gif" border="0">(<img src="book-Z-G-D-11.gif" border="0"><sup><em>n</em></sup>) steps and space <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>), where <img src="book-Z-G-D-11.gif" border="0"> is the
golden ratio described in section&nbsp;<a href="#%_sec_1.2.2">1.2.2</a>.<p>


Orders of growth provide only a crude description of the behavior of a
process.  For example, a process requiring <em>n</em><sup>2</sup> steps and a process
requiring 1000<em>n</em><sup>2</sup> steps and a process requiring 3<em>n</em><sup>2</sup> + 10<em>n</em> + 17 steps
all have <img src="book-Z-G-D-3.gif" border="0">(<em>n</em><sup>2</sup>) order of growth.  On the other hand, order of
growth provides a useful indication of how we may expect the behavior
of the process to change as we change the size of the problem.  For a
<a name="%_idx_780"></a><img src="book-Z-G-D-3.gif" border="0">(<em>n</em>) (linear) process, doubling the size will roughly double the amount
of resources used.  For an <a name="%_idx_782"></a>exponential process, each increment in
problem size will multiply the resource utilization by a constant
factor.  In the remainder of section&nbsp;<a href="#%_sec_1.2">1.2</a>
we will examine two
algorithms whose order of growth is <a name="%_idx_784"></a>logarithmic, so that doubling the
problem size increases the resource requirement by a constant amount.<p>

<p><a name="%_thm_1.14"></a>
<b>Exercise 1.14.</b>&nbsp;&nbsp;Draw the tree illustrating the process generated by the <tt>count-change</tt> procedure of section&nbsp;<a href="#%_sec_1.2.2">1.2.2</a> in making
change for 11 cents.  What are the orders of growth of the space and
number of steps used by this process as the amount to be changed
increases?
<p><p>

<p><a name="%_thm_1.15"></a>
<b>Exercise 1.15.</b>&nbsp;&nbsp;<a name="%_idx_786"></a>The sine of an angle (specified in
radians) can be computed by making use of the approximation
<tt>sin</tt> <em>x</em> <img src="book-Z-G-D-20.gif" border="0">  <em>x</em>
if <em>x</em> is
sufficiently small, and the trigonometric identity 
<p><div align=left><img src="ch1-Z-G-19.gif" border="0"></div><p> 
to reduce the size of the argument of <tt>sin</tt>.  (For
purposes of this exercise an angle is considered ``sufficiently
small'' if its magnitude is not greater than 0.1 radians.) These
ideas are incorporated in the following procedures:<p>

<p><p><tt><a name="%_idx_788"></a>(define&nbsp;(cube&nbsp;x)&nbsp;(*&nbsp;x&nbsp;x&nbsp;x))<br>
(define&nbsp;(p&nbsp;x)&nbsp;(-&nbsp;(*&nbsp;3&nbsp;x)&nbsp;(*&nbsp;4&nbsp;(cube&nbsp;x))))<br>
(define&nbsp;(sine&nbsp;angle)<br>
&nbsp;&nbsp;&nbsp;(if&nbsp;(not&nbsp;(&gt;&nbsp;(abs&nbsp;angle)&nbsp;0.1))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;angle<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(p&nbsp;(sine&nbsp;(/&nbsp;angle&nbsp;3.0)))))<br>
</tt><p><p><p>

a.&nbsp;&nbsp;How many times is the procedure <tt>p</tt> 
applied when <tt>(sine 12.15)</tt> is evaluated?<p>

b.&nbsp;&nbsp;What is the order of growth in space and number of steps (as a
function of&nbsp;<em>a</em>) used by the process generated by the <tt>sine</tt>
procedure when <tt>(sine a)</tt> is evaluated?
<p><p>

<a name="%_sec_1.2.4"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.2.4">1.2.4&nbsp;&nbsp;Exponentiation</a></h3><p>


<a name="%_idx_790"></a>

Consider the problem of computing the exponential of a given number.
We would like a procedure that takes as arguments a base <em>b</em> and a
positive integer exponent <em>n</em> and computes <em>b</em><sup><em>n</em></sup>.  One way to do this
is via the recursive definition
<p><div align=left><img src="ch1-Z-G-20.gif" border="0"></div><p>
which translates readily into the procedure <p>

<p><p><tt><a name="%_idx_792"></a>(define&nbsp;(expt&nbsp;b&nbsp;n)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;n&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;b&nbsp;(expt&nbsp;b&nbsp;(-&nbsp;n&nbsp;1)))))<br>
</tt><p><p>
This is a linear recursive process, which requires <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>) steps
and <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>) space.  Just as with factorial, we can readily
formulate an equivalent linear iteration:<p>


<p><p><tt><a name="%_idx_794"></a>(define&nbsp;(expt&nbsp;b&nbsp;n)<br>
&nbsp;&nbsp;(expt-iter&nbsp;b&nbsp;n&nbsp;1))<br>
<br>
(define&nbsp;(expt-iter&nbsp;b&nbsp;counter&nbsp;product)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;counter&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;product<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(expt-iter&nbsp;b<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;counter&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;b&nbsp;product))))&nbsp;<br>
</tt><p><p>
This version requires <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>) steps and <img src="book-Z-G-D-3.gif" border="0">(1) space.<p>

<a name="%_idx_796"></a>We can compute exponentials in fewer steps by using successive
squaring.  For instance, rather than computing <em>b</em><sup>8</sup> as
<p><div align=left><img src="ch1-Z-G-21.gif" border="0"></div><p>
we can compute it using three multiplications:
<p><div align=left><img src="ch1-Z-G-22.gif" border="0"></div><p><p>

This method works fine for exponents that are powers of 2.  We can
also take advantage of successive squaring in computing exponentials
in general if we use the rule<p>

<p><div align=left><img src="ch1-Z-G-23.gif" border="0"></div><p>
We can express this method as a procedure:<p>


<p><p><tt><a name="%_idx_798"></a>(define&nbsp;(fast-expt&nbsp;b&nbsp;n)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;n&nbsp;0)&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((even?&nbsp;n)&nbsp;(square&nbsp;(fast-expt&nbsp;b&nbsp;(/&nbsp;n&nbsp;2))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(*&nbsp;b&nbsp;(fast-expt&nbsp;b&nbsp;(-&nbsp;n&nbsp;1))))))<br>
</tt><p><p>
where the predicate to test whether an integer is even is defined in terms of
the <a name="%_idx_800"></a><a name="%_idx_802"></a>primitive procedure <tt>remainder</tt> by
<p>


<p><p><tt><a name="%_idx_804"></a>(define&nbsp;(even?&nbsp;n)<br>
&nbsp;&nbsp;(=&nbsp;(remainder&nbsp;n&nbsp;2)&nbsp;0))<br>
</tt><p><p>
<a name="%_idx_806"></a><a name="%_idx_808"></a>The process evolved by <tt>fast-expt</tt> grows logarithmically with <em>n</em>
in both space and number of steps.  To see this, observe that
computing <em>b</em><sup>2<em>n</em></sup> using <tt>fast-expt</tt> requires only one more
multiplication than computing <em>b</em><sup><em>n</em></sup>.  The size of the exponent we can
compute therefore doubles (approximately) with every new
multiplication we are allowed.  Thus, the number of multiplications
required for an exponent of <em>n</em> grows about as fast as the logarithm
of <em>n</em> to the base 2.  The process has <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>)
growth.<a name="call_footnote_Temp_62" href="#footnote_Temp_62"><sup><small>37</small></sup></a><p>

The difference between <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>) growth and <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>) growth
becomes striking as <em>n</em> becomes large.  For example, <tt>fast-expt</tt>
for <em>n</em> = 1000 requires only 14 multiplications.<a name="call_footnote_Temp_63" href="#footnote_Temp_63"><sup><small>38</small></sup></a> It is also possible to use the idea of
successive squaring to devise an iterative algorithm that computes
exponentials with a logarithmic number of steps
(see exercise&nbsp;<a href="#%_thm_1.16">1.16</a>), although, as is often
the case with iterative algorithms, this is not written down so
straightforwardly as the recursive algorithm.<a name="call_footnote_Temp_64" href="#footnote_Temp_64"><sup><small>39</small></sup></a>

<p>

<p><a name="%_thm_1.16"></a>
<b>Exercise 1.16.</b>&nbsp;&nbsp;Design a procedure that evolves an iterative exponentiation process
that uses successive squaring and uses a logarithmic number of steps,
as does <tt>fast-expt</tt>.  (Hint: Using the observation that
(<em>b</em><sup><em>n</em>/2</sup>)<sup>2</sup>  = (<em>b</em><sup>2</sup>)<sup><em>n</em>/2</sup>, keep, along with the exponent <em>n</em> and the
base <em>b</em>, an additional state variable <em>a</em>, and define the state
transformation in such a way that the product <em>a</em> <em>b</em><sup><em>n</em></sup> is unchanged
from state to state.  At the beginning of the process <em>a</em> is taken to
be 1, and the answer is given by the value of <em>a</em> at the end of the
process.  In general, the technique of defining an <a name="%_idx_816"></a><em>invariant
quantity</em> that remains unchanged from state to state is a powerful way
to think about the <a name="%_idx_818"></a>design of iterative algorithms.)

<p><p>

<p><a name="%_thm_1.17"></a>
<b>Exercise 1.17.</b>&nbsp;&nbsp;The exponentiation algorithms in this section are based on performing
exponentiation by means of repeated multiplication.  In a similar way,
one can perform integer multiplication by means of repeated addition.
The following multiplication procedure (in which it is assumed that
our language can only add, not multiply) is analogous to the <tt>expt</tt> procedure:<p>

<p><p><tt>(define&nbsp;(*&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;b&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;a&nbsp;(*&nbsp;a&nbsp;(-&nbsp;b&nbsp;1)))))<br>
</tt><p><p>

This algorithm takes a number of steps that is linear in <tt>b</tt>.
Now suppose we include, together with addition, operations <tt>double</tt>,
which doubles an integer, and <tt>halve</tt>, which divides an (even)
integer by 2.  Using these, design a multiplication procedure analogous
to <tt>fast-expt</tt> that uses a logarithmic number of steps. 
<p><p>

<p><a name="%_thm_1.18"></a>
<b>Exercise 1.18.</b>&nbsp;&nbsp;Using the results of exercises&nbsp;<a href="#%_thm_1.16">1.16</a>
and&nbsp;<a href="#%_thm_1.17">1.17</a>, devise a procedure that generates an iterative
process for multiplying two integers in terms of adding, doubling, and
halving and uses a logarithmic number of steps.<a name="call_footnote_Temp_68" href="#footnote_Temp_68"><sup><small>40</small></sup></a>

<p><p>

<p><a name="%_thm_1.19"></a>
<b>Exercise 1.19.</b>&nbsp;&nbsp;
<a name="%_idx_828"></a>There is a clever algorithm for computing the Fibonacci numbers in
a logarithmic number of steps.
Recall the transformation of the state variables
<em>a</em> and <em>b</em> in the <tt>fib-iter</tt> process of
section&nbsp;<a href="#%_sec_1.2.2">1.2.2</a>: <em>a</em> <img src="book-Z-G-D-14.gif" border="0">  <em>a</em> + <em>b</em> and <em>b</em> <img src="book-Z-G-D-14.gif" border="0"> 
<em>a</em>.  Call this transformation <em>T</em>, and observe that applying <em>T</em> over
and over again <em>n</em> times, starting with 1 and 0, produces the pair
 <em>F</em><em>i</em><em>b</em>(<em>n</em> + 1) and  <em>F</em><em>i</em><em>b</em>(<em>n</em>).  In other words, the Fibonacci
numbers are produced by applying <em>T</em><sup><em>n</em></sup>, the <em>n</em>th power of the
transformation <em>T</em>, starting with the pair (1,0).  Now consider <em>T</em>
to be the special case of <em>p</em> = 0 and <em>q</em> = 1 in a family of
transformations <em>T</em><sub><em>p</em><em>q</em></sub>, where <em>T</em><sub><em>p</em><em>q</em></sub> transforms the pair (<em>a</em>,<em>b</em>)
according to <em>a</em> <img src="book-Z-G-D-14.gif" border="0">  <em>b</em><em>q</em> + <em>a</em><em>q</em> + <em>a</em><em>p</em> and <em>b</em> <img src="book-Z-G-D-14.gif" border="0">  <em>b</em><em>p</em> + <em>a</em><em>q</em>.  Show
that if we apply such a transformation <em>T</em><sub><em>p</em><em>q</em></sub> twice, the effect is
the same as using a single transformation <em>T</em><sub><em>p</em>'<em>q</em>'</sub> of the same form,
and compute <em>p</em>' and <em>q</em>' in terms of <em>p</em> and&nbsp;<em>q</em>.  This gives us an
explicit way to square these transformations, and thus we can compute
<em>T</em><sup><em>n</em></sup> using successive squaring, as in the <tt>fast-expt</tt>
procedure.  Put this all together to complete the following procedure,
which runs in a logarithmic number of steps:<a name="call_footnote_Temp_70" href="#footnote_Temp_70"><sup><small>41</small></sup></a><p>

<p><p><tt>(define&nbsp;(fib&nbsp;n)<br>
&nbsp;&nbsp;(fib-iter&nbsp;1&nbsp;0&nbsp;0&nbsp;1&nbsp;n))<br>
(define&nbsp;(fib-iter&nbsp;a&nbsp;b&nbsp;p&nbsp;q&nbsp;count)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;count&nbsp;0)&nbsp;b)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((even?&nbsp;count)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fib-iter&nbsp;a<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>??</em>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<em>;&nbsp;compute&nbsp;<em>p</em>'</em><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>??</em>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<em>;&nbsp;compute&nbsp;<em>q</em>'</em><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(/&nbsp;count&nbsp;2)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(fib-iter&nbsp;(+&nbsp;(*&nbsp;b&nbsp;q)&nbsp;(*&nbsp;a&nbsp;q)&nbsp;(*&nbsp;a&nbsp;p))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(*&nbsp;b&nbsp;p)&nbsp;(*&nbsp;a&nbsp;q))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;count&nbsp;1)))))<br>
</tt><p><p>
<p><p>

<a name="%_sec_1.2.5"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.2.5">1.2.5&nbsp;&nbsp;Greatest Common Divisors</a></h3><p>


<a name="%_idx_834"></a>
The greatest common divisor (GCD) of two integers <em>a</em> and <em>b</em> is
defined to be the largest integer that divides both <em>a</em> and
<em>b</em> with no remainder.  For example, the GCD of 16 and 28 is 4.  In chapter&nbsp;2,
when we investigate how to implement rational-number arithmetic, we
will need to be able to compute GCDs in order to reduce
rational numbers to lowest terms.  (To reduce a rational number to
lowest terms, we must divide both the numerator and the denominator by their
GCD.  For example, 16/28 reduces to 4/7.)  One way to find the
GCD of two integers is to factor them and search for common
factors, but there is a famous algorithm that is much more efficient.<p>

<a name="%_idx_836"></a>The idea of the algorithm is based on the observation that, if <em>r</em> is
the remainder when <em>a</em> is divided by <em>b</em>, then the common divisors of
<em>a</em> and <em>b</em> are precisely the same as the common divisors of <em>b</em> and
<em>r</em>.  Thus, we can use the equation
<p><div align=left><img src="ch1-Z-G-24.gif" border="0"></div><p>
to successively reduce the problem of computing a GCD to the
problem of computing the GCD of smaller and smaller pairs of
integers.  For example,
<p><div align=left><img src="ch1-Z-G-25.gif" border="0"></div><p>
reduces GCD(206,40) to GCD(2,0), which is 2.  It is
possible to show that starting with any two positive integers and
performing repeated reductions will always eventually produce a pair
where the second number is 0.  Then the GCD is the other
number in the pair.  This method for computing the GCD is
known as <em>Euclid's Algorithm</em>.<a name="call_footnote_Temp_71" href="#footnote_Temp_71"><sup><small>42</small></sup></a><p>

It is easy to express Euclid's Algorithm as a procedure:
<p><p><tt><a name="%_idx_842"></a>(define&nbsp;(gcd&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(if&nbsp;(=&nbsp;b&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(gcd&nbsp;b&nbsp;(remainder&nbsp;a&nbsp;b))))<br>
</tt><p><p>
This generates an iterative process, whose number of steps grows as
the logarithm of the numbers involved.<p>

<a name="%_idx_844"></a>The fact that the number of steps required by Euclid's Algorithm has
logarithmic growth bears an interesting relation to the Fibonacci
numbers:<p>

<p><p><a name="%_idx_846"></a><a name="%_idx_848"></a><strong>Lam&eacute;'s Theorem:</strong> If Euclid's Algorithm requires <em>k</em> steps to
compute the GCD of some pair, then the smaller number in the pair
must be greater than or equal to the <em>k</em>th Fibonacci
number.<a name="call_footnote_Temp_72" href="#footnote_Temp_72"><sup><small>43</small></sup></a><p>

<p><p><p>

We can use this theorem to get an order-of-growth estimate for Euclid's
Algorithm.  Let <em>n</em> be the smaller of the two inputs to the
procedure.  If the process takes <em>k</em> steps, then we must have 
<em>n</em><u>&gt;</u>  <em>F</em><em>i</em><em>b</em> (<em>k</em>) <img src="book-Z-G-D-20.gif" border="0"> <img src="book-Z-G-D-11.gif" border="0"><sup><em>k</em></sup>/<img src="book-Z-G-D-13.gif" border="0">5.  Therefore
the number of steps <em>k</em> grows as the logarithm (to the base
<img src="book-Z-G-D-11.gif" border="0">) of <em>n</em>.  Hence, the order of growth is <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>).<p>

<p><a name="%_thm_1.20"></a>
<b>Exercise 1.20.</b>&nbsp;&nbsp;<a name="%_idx_852"></a><a name="%_idx_854"></a>The process that a procedure generates is of course dependent on the
rules used by the interpreter.  As an example, consider the iterative
<tt>gcd</tt> procedure given above.
Suppose we were to interpret this procedure using normal-order
evaluation, as discussed in section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>.
(The normal-order-evaluation rule for <tt>if</tt> is described in
exercise&nbsp;<a href="book-Z-H-10.html#%_thm_1.5">1.5</a>.)  Using the
substitution method (for normal order), illustrate the process
generated in evaluating <tt>(gcd 206 40)</tt> and indicate the
<tt>remainder</tt> operations that are actually performed.
How many <tt>remainder</tt> operations are actually performed
in the normal-order evaluation of <tt>(gcd 206&nbsp;40)</tt>?
In the applicative-order evaluation?
<p><p>

<a name="%_sec_1.2.6"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_1.2.6">1.2.6&nbsp;&nbsp;Example: Testing for Primality</a></h3><p>


<a name="%_idx_856"></a><a name="%_idx_858"></a>
This section describes two methods for checking the primality of an
integer <em>n</em>, one with order of growth <img src="book-Z-G-D-3.gif" border="0">(<img src="book-Z-G-D-13.gif" border="0"><em>n</em>), and a
``probabilistic'' algorithm with order of growth <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>).  The
exercises at the end of this section suggest programming
projects based on these algorithms.<p>

<a name="%_sec_Temp_74"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_74">Searching for divisors</a></h4><p>

Since ancient times, mathematicians have been fascinated by problems
concerning prime numbers, and many people have worked on the problem
of determining ways to test if numbers are prime.  One way
to test if a number is prime is to find the number's divisors.  The
following program finds the smallest integral divisor (greater than 1)
of a given number&nbsp;<em>n</em>.  It does this in a straightforward way, by
testing <em>n</em> for divisibility by successive integers starting with 2.<p>

<p><p><tt><a name="%_idx_860"></a>(define&nbsp;(smallest-divisor&nbsp;n)<br>
&nbsp;&nbsp;(find-divisor&nbsp;n&nbsp;2))<br>
<a name="%_idx_862"></a>(define&nbsp;(find-divisor&nbsp;n&nbsp;test-divisor)<br>
&nbsp;&nbsp;(cond&nbsp;((&gt;&nbsp;(square&nbsp;test-divisor)&nbsp;n)&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((divides?&nbsp;test-divisor&nbsp;n)&nbsp;test-divisor)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(find-divisor&nbsp;n&nbsp;(+&nbsp;test-divisor&nbsp;1)))))<br>
<a name="%_idx_864"></a>(define&nbsp;(divides?&nbsp;a&nbsp;b)<br>
&nbsp;&nbsp;(=&nbsp;(remainder&nbsp;b&nbsp;a)&nbsp;0))<br>
</tt><p><p><p>

We can test whether a number is prime as follows: <em>n</em> is prime if
and only if <em>n</em> is its own smallest divisor.<p>

<p><p><tt><a name="%_idx_866"></a>(define&nbsp;(prime?&nbsp;n)<br>
&nbsp;&nbsp;(=&nbsp;n&nbsp;(smallest-divisor&nbsp;n)))<br>
</tt><p><p><p>

The end test for <tt>find-divisor</tt> is based on the fact that if <em>n</em>
is not prime it must have a divisor less than or equal to
<img src="book-Z-G-D-13.gif" border="0"><em>n</em>.<a name="call_footnote_Temp_75" href="#footnote_Temp_75"><sup><small>44</small></sup></a>  This
means that the algorithm need only test divisors between 1 and
<img src="book-Z-G-D-13.gif" border="0"><em>n</em>.  Consequently, the number of steps required to identify
<em>n</em> as prime will have order of growth <img src="book-Z-G-D-3.gif" border="0">(<img src="book-Z-G-D-13.gif" border="0"><em>n</em>).<p>

<a name="%_sec_Temp_76"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_76">The Fermat test</a></h4><p>

<a name="%_idx_868"></a><a name="%_idx_870"></a>The <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>) primality test is based on a result from number
theory known as Fermat's Little Theorem.<a name="call_footnote_Temp_77" href="#footnote_Temp_77"><sup><small>45</small></sup></a><p>

<p><p><a name="%_idx_886"></a><strong>Fermat's Little Theorem:</strong> If <em>n</em> is a prime number and 
<em>a</em> is any positive integer less than <em>n</em>, then <em>a</em> raised to the
<em>n</em>th power is congruent to <em>a</em> modulo <em>n</em>.<p>

<p><p><a name="%_idx_888"></a>(Two numbers are said to be <em>congruent modulo</em> <em>n</em> if
they both have the same remainder when divided by <em>n</em>.  The
remainder of a number <em>a</em> when divided by <em>n</em> is also referred to as
the <a name="%_idx_890"></a><a name="%_idx_892"></a><em>remainder of</em> <em>a</em> <em>modulo</em> <em>n</em>, or simply as <em>a</em> 
<em>modulo</em> <em>n</em>.)<p>

If <em>n</em> is not prime, then, in general, most of the numbers <em>a</em>&lt; <em>n</em> will not
satisfy the above relation.  This leads to the following algorithm for
testing primality: Given a number <em>n</em>, pick a <a name="%_idx_894"></a>random number <em>a</em> &lt; <em>n</em> and
compute the remainder of <em>a</em><sup><em>n</em></sup> modulo <em>n</em>.  If the result is not equal to
<em>a</em>, then <em>n</em> is certainly not prime.  If it is <em>a</em>, then chances are good
that <em>n</em> is prime.  Now pick another random number <em>a</em> and test it with the
same method.  If it also satisfies the equation, then we can be even more
confident that <em>n</em> is prime.  By trying more and more values of <em>a</em>, we can
increase our confidence in the result.  This algorithm is known as the
Fermat test.<p>

<a name="%_idx_896"></a>To implement the Fermat test, we need a procedure that computes the
exponential of a number modulo another number:<p>

<p><p><tt><a name="%_idx_898"></a>(define&nbsp;(expmod&nbsp;base&nbsp;exp&nbsp;m)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;exp&nbsp;0)&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((even?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(remainder&nbsp;(square&nbsp;(expmod&nbsp;base&nbsp;(/&nbsp;exp&nbsp;2)&nbsp;m))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(remainder&nbsp;(*&nbsp;base&nbsp;(expmod&nbsp;base&nbsp;(-&nbsp;exp&nbsp;1)&nbsp;m))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m))))&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<br>
</tt><p><p>
This is very similar to the <tt>fast-expt</tt> procedure of
section&nbsp;<a href="#%_sec_1.2.4">1.2.4</a>.  It uses successive squaring, so
that the number of steps grows logarithmically with the
exponent.<a name="call_footnote_Temp_78" href="#footnote_Temp_78"><sup><small>46</small></sup></a><p>

The Fermat test is performed by choosing at random a number <em>a</em>
between 1 and <em>n</em> - 1 inclusive and checking whether the remainder
modulo <em>n</em> of the <em>n</em>th power of <em>a</em> is equal to <em>a</em>.  The random
number <em>a</em> is chosen using the procedure <a name="%_idx_900"></a><a name="%_idx_902"></a><tt>random</tt>, which we assume is
included as a primitive in Scheme. <tt>Random</tt> returns a
nonnegative integer less than its integer input.  Hence, to obtain a random
number between 1 and <em>n</em> - 1, we call <tt>random</tt> with an input of
<em>n</em> - 1 and add 1 to the result:<p>

<p><p><tt><a name="%_idx_904"></a>(define&nbsp;(fermat-test&nbsp;n)<br>
&nbsp;&nbsp;(define&nbsp;(try-it&nbsp;a)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(=&nbsp;(expmod&nbsp;a&nbsp;n&nbsp;n)&nbsp;a))<br>
&nbsp;&nbsp;(try-it&nbsp;(+&nbsp;1&nbsp;(random&nbsp;(-&nbsp;n&nbsp;1)))))<br>
</tt><p><p><p>

The following procedure runs the test a given number of times, as
specified by a parameter.  Its value is true if the test succeeds
every time, and false otherwise.<p>

<p><p><tt><a name="%_idx_906"></a>(define&nbsp;(fast-prime?&nbsp;n&nbsp;times)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;times&nbsp;0)&nbsp;true)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((fermat-test&nbsp;n)&nbsp;(fast-prime?&nbsp;n&nbsp;(-&nbsp;times&nbsp;1)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;false)))<br>
</tt><p><p><p>

<a name="%_sec_Temp_79"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_79">Probabilistic methods</a></h4><p>

<a name="%_idx_908"></a><a name="%_idx_910"></a>
The Fermat test differs in character from most familiar algorithms, in
which one computes an answer that is guaranteed to be correct.  Here,
the answer obtained is only probably correct.  More precisely, if <em>n</em>
ever fails the Fermat test, we can be certain that <em>n</em> is not prime.
But the fact that <em>n</em> passes the test, while an extremely strong
indication, is still not a guarantee that <em>n</em> is prime.  What we would
like to say is that for any number <em>n</em>, if we perform the test enough
times and find that <em>n</em> always passes the test, then the probability
of error in our primality test can be made as small as we like.<p>


Unfortunately, this assertion is not quite correct.  There do exist
numbers that fool the Fermat test: numbers <em>n</em> that are not prime and
yet have the property that <em>a</em><sup><em>n</em></sup> is congruent to <em>a</em> modulo <em>n</em> for
all integers <em>a</em> &lt; <em>n</em>.  Such numbers are extremely rare, so the Fermat
test is quite reliable in practice.<a name="call_footnote_Temp_80" href="#footnote_Temp_80"><sup><small>47</small></sup></a>
There are variations of the Fermat test that cannot be fooled.  In
these tests, as with the Fermat method, one tests the primality of an
integer <em>n</em> by choosing a random integer <em>a</em>&lt;<em>n</em> and checking some
condition that depends upon <em>n</em> and <em>a</em>.  (See
exercise&nbsp;<a href="#%_thm_1.28">1.28</a> for an example of such a test.)  On the
other hand, in contrast to the Fermat test, one can prove that, for
any <em>n</em>, the condition does not hold for most of the integers <em>a</em>&lt;<em>n</em>
unless <em>n</em> is prime.  Thus, if <em>n</em> passes the test for some random
choice of&nbsp;<em>a</em>, the chances are better than even that <em>n</em> is prime.  If
<em>n</em> passes the test for two random choices of <em>a</em>, the chances are better
than 3 out of 4 that <em>n</em> is prime. By running the test with more and
more randomly chosen values of <em>a</em> we can make the probability of
error as small as we like.<p>

The existence of tests for which one can prove that the chance of
error becomes arbitrarily small has sparked interest in algorithms of
this type, which have come to be known as <em>probabilistic
algorithms</em>.  There is a great deal of research activity in this area,
and probabilistic algorithms have been fruitfully applied to many
fields.<a name="call_footnote_Temp_81" href="#footnote_Temp_81"><sup><small>48</small></sup></a><p>

<p><a name="%_thm_1.21"></a>
<b>Exercise 1.21.</b>&nbsp;&nbsp;Use the <tt>smallest-divisor</tt> procedure to find the smallest divisor
of each of the following numbers: 199, 1999, 19999.
<p><p>

<p><a name="%_thm_1.22"></a>
<b>Exercise 1.22.</b>&nbsp;&nbsp;<a name="%_idx_932"></a><a name="%_idx_934"></a>Most Lisp implementations include a primitive called <tt>runtime</tt>
that returns an integer that specifies the amount of time the system
has been running (measured, for example, in microseconds).  The
following <tt>timed-prime-test</tt> procedure, when called with an
integer <em>n</em>, prints <em>n</em> and checks to see if <em>n</em> is prime.  If <em>n</em> is
prime, the procedure prints three asterisks followed by the amount of time
used in performing the test.<p>

<p><p><tt><a name="%_idx_936"></a><a name="%_idx_938"></a><a name="%_idx_940"></a>(define&nbsp;(timed-prime-test&nbsp;n)<br>
&nbsp;&nbsp;(newline)<br>
&nbsp;&nbsp;(display&nbsp;n)<br>
&nbsp;&nbsp;(start-prime-test&nbsp;n&nbsp;(runtime)))<br>
(define&nbsp;(start-prime-test&nbsp;n&nbsp;start-time)<br>
&nbsp;&nbsp;(if&nbsp;(prime?&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(report-prime&nbsp;(-&nbsp;(runtime)&nbsp;start-time))))<br>
(define&nbsp;(report-prime&nbsp;elapsed-time)<br>
&nbsp;&nbsp;(display&nbsp;&quot;&nbsp;***&nbsp;&quot;)<br>
&nbsp;&nbsp;(display&nbsp;elapsed-time))<br>
</tt><p><p>
Using this procedure, write a procedure <tt>search-for-primes</tt> that
checks the primality of consecutive odd integers in a specified range.
Use your procedure to find the three smallest primes larger than 1000;
larger than 10,000; larger than 100,000; larger than 1,000,000.  Note
the time needed to test each prime.  Since the testing algorithm has
order of growth of <img src="book-Z-G-D-3.gif" border="0">(<img src="book-Z-G-D-13.gif" border="0"><em>n</em>), you should expect that testing
for primes around 10,000 should take about <img src="book-Z-G-D-13.gif" border="0">10 times as long
as testing for primes around 1000.  Do your timing data bear this out?
How well do the data for 100,000 and 1,000,000 support the <img src="book-Z-G-D-13.gif" border="0"><em>n</em>
prediction?  Is your result compatible with the notion that programs
on your machine run in time proportional to the number of steps
required for the computation?

<p><p>

<p><a name="%_thm_1.23"></a>
<b>Exercise 1.23.</b>&nbsp;&nbsp;<a name="%_idx_942"></a>The <tt>smallest-divisor</tt> procedure shown at the start of this section
does lots of needless testing: After it checks to see if the
number is divisible by 2 there is no point in checking to see if
it is divisible by any larger even numbers.  This suggests that the
values used for <tt>test-divisor</tt> should not be 2, 3, 4, 5, 6,
<tt>...</tt>, but rather 2, 3, 5, 7, 9, <tt>...</tt>.  To implement this
change, define a procedure <tt>next</tt> that returns 3 if its input is
equal to 2 and otherwise returns its input plus&nbsp;2.  Modify the <tt>smallest-divisor</tt> procedure to use <tt>(next test-divisor)</tt> instead
of <tt>(+ test-divisor 1)</tt>.  With <tt>timed-prime-test</tt>
incorporating this modified version of <tt>smallest-divisor</tt>, run the
test for each of the 12 primes found in
exercise&nbsp;<a href="#%_thm_1.22">1.22</a>.  Since this modification halves the
number of test steps, you should expect it to run about twice as fast.
Is this expectation confirmed?  If not, what is the observed ratio of
the speeds of the two algorithms, and how do you explain the fact that
it is different from 2?
<p><p>

<p><a name="%_thm_1.24"></a>
<b>Exercise 1.24.</b>&nbsp;&nbsp;Modify the <tt>timed-prime-test</tt> procedure of
exercise&nbsp;<a href="#%_thm_1.22">1.22</a> to use <tt>fast-prime?</tt> (the
Fermat method), and test each of the 12 primes you found in that
exercise.  Since the Fermat test has <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>) growth, how
would you expect the time to test primes near 1,000,000 to compare
with the time needed to test primes near 1000?  Do your data bear this
out?  Can you explain any discrepancy you find?

<p><p>

<p><a name="%_thm_1.25"></a>
<b>Exercise 1.25.</b>&nbsp;&nbsp;Alyssa P. Hacker complains that we went to a lot of extra work in
writing <tt>expmod</tt>.  After all, she says, since we already know how
to compute exponentials, we could have simply written<p>

<p><p><tt><a name="%_idx_944"></a>(define&nbsp;(expmod&nbsp;base&nbsp;exp&nbsp;m)<br>
&nbsp;&nbsp;(remainder&nbsp;(fast-expt&nbsp;base&nbsp;exp)&nbsp;m))<br>
</tt><p><p>
Is she correct?  Would this procedure serve as well for our fast prime
tester?  Explain.

<p><p>

<p><a name="%_thm_1.26"></a>
<b>Exercise 1.26.</b>&nbsp;&nbsp;Louis Reasoner is having great difficulty doing
exercise&nbsp;<a href="#%_thm_1.24">1.24</a>.  His <tt>fast-prime?</tt> test
seems to run more slowly than his <tt>prime?</tt> test.  Louis calls his
friend Eva Lu Ator over to help.  When they examine Louis's code, they
find that he has rewritten the <tt>expmod</tt> procedure to use an
explicit multiplication, rather than calling <tt>square</tt>:<p>

<p><p><tt><a name="%_idx_946"></a>(define&nbsp;(expmod&nbsp;base&nbsp;exp&nbsp;m)<br>
&nbsp;&nbsp;(cond&nbsp;((=&nbsp;exp&nbsp;0)&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((even?&nbsp;exp)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(remainder&nbsp;(*&nbsp;(expmod&nbsp;base&nbsp;(/&nbsp;exp&nbsp;2)&nbsp;m)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(expmod&nbsp;base&nbsp;(/&nbsp;exp&nbsp;2)&nbsp;m))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(remainder&nbsp;(*&nbsp;base&nbsp;(expmod&nbsp;base&nbsp;(-&nbsp;exp&nbsp;1)&nbsp;m))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m))))<br>
</tt><p><p>
``I don't see what difference that could make,'' says Louis.  ``I
do.''  says Eva.  ``By writing the procedure like that, you have
transformed the <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>) process into a <img src="book-Z-G-D-3.gif" border="0">(<em>n</em>) process.''
Explain.
<p><p>

<p><a name="%_thm_1.27"></a>
<b>Exercise 1.27.</b>&nbsp;&nbsp;<a name="%_idx_948"></a>Demonstrate that the Carmichael numbers listed in
footnote&nbsp;<a href="#footnote_Temp_80">47</a> really do fool
the Fermat test.  That is, write a procedure that takes an integer <em>n</em>
and tests whether <em>a</em><sup><em>n</em></sup> is congruent to <em>a</em> modulo <em>n</em> for every
<em>a</em>&lt;<em>n</em>, and try your procedure on the given Carmichael numbers.
<p><p>


<p><a name="%_thm_1.28"></a>
<b>Exercise 1.28.</b>&nbsp;&nbsp;<a name="%_idx_950"></a><a name="%_idx_952"></a><a name="%_idx_954"></a><a name="%_idx_956"></a><a name="%_idx_958"></a>One variant of the Fermat test that cannot be fooled is called the
<em>Miller-Rabin test</em> (Miller 1976; Rabin 1980).  This starts from
<a name="%_idx_960"></a>an alternate form of Fermat's Little Theorem, which states that if <em>n</em>
is a prime number and <em>a</em> is any positive integer less than <em>n</em>, then
<em>a</em> raised to the (<em>n</em> - 1)st power is congruent to 1 modulo&nbsp;<em>n</em>.  To test
the primality of a number <em>n</em> by the Miller-Rabin test, we pick a
random number <em>a</em>&lt;<em>n</em> and raise <em>a</em> to the (<em>n</em> - 1)st power modulo&nbsp;<em>n</em>
using the <tt>expmod</tt> procedure.  However, whenever we perform the
squaring step in <tt>expmod</tt>, we check to see if we have discovered a
``nontrivial square root of 1 modulo&nbsp;<em>n</em>,'' that is, a number not
equal to 1 or <em>n</em> - 1 whose square is equal to 1 modulo&nbsp;<em>n</em>.  It is
possible to prove that if such a nontrivial square root of 1 exists,
then <em>n</em> is not prime.  It is also possible to prove that if <em>n</em> is an
odd number that is not prime, then, for at least half the numbers
<em>a</em>&lt;<em>n</em>, computing <em>a</em><sup><em>n</em>-1</sup> in this way will reveal a nontrivial
square root of 1 modulo&nbsp;<em>n</em>.  (This is why the Miller-Rabin test
cannot be fooled.)  Modify the <tt>expmod</tt> procedure to signal if it
discovers a nontrivial square root of 1, and use this to implement
the Miller-Rabin test with a procedure analogous to <tt>fermat-test</tt>.
Check your procedure by testing various known primes and non-primes.
Hint: One convenient way to make <tt>expmod</tt> signal is to have it
return 0.

<p><p>

<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_46" href="#call_footnote_Temp_46"><sup><small>29</small></sup></a> In a real program we would probably use the
block structure introduced in the last section to hide the definition
of <tt>fact-iter</tt>:
<p><p><tt>(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;(define&nbsp;(iter&nbsp;product&nbsp;counter)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;counter&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;product<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;(*&nbsp;counter&nbsp;product)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;counter&nbsp;1))))<br>
&nbsp;&nbsp;(iter&nbsp;1&nbsp;1))<br>
</tt><p><p>
We avoided doing this here so as to minimize the number of things to
think about at once.

<p><a name="footnote_Temp_47" href="#call_footnote_Temp_47"><sup><small>30</small></sup></a> When we discuss the implementation of
procedures on register machines in chapter&nbsp;5, we will see that any
iterative process can be realized ``in hardware'' as a machine that
has a fixed set of registers and no auxiliary memory.  In contrast,
realizing a recursive process requires a machine that uses an
<a name="%_idx_678"></a>auxiliary data structure known as a <em>stack</em>.

<p><a name="footnote_Temp_48" href="#call_footnote_Temp_48"><sup><small>31</small></sup></a> Tail recursion has long been
<a name="%_idx_698"></a><a name="%_idx_700"></a><a name="%_idx_702"></a>known as a compiler optimization trick.  A coherent semantic basis for
tail recursion was provided by Carl Hewitt (1977), who explained it in
<a name="%_idx_704"></a>terms of the ``message-passing'' model of computation that we shall
discuss in chapter&nbsp;3. Inspired by this, Gerald Jay Sussman and Guy
Lewis Steele Jr. (see Steele 1975) constructed a tail-recursive
interpreter for Scheme.  Steele later showed how tail recursion is a
consequence of the natural way to compile procedure calls (Steele
1977).  The IEEE standard for Scheme requires that Scheme implementations
<a name="%_idx_706"></a>be tail-recursive.

<p><a name="footnote_Temp_51" href="#call_footnote_Temp_51"><sup><small>32</small></sup></a> An example of this was hinted
at in section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.3">1.1.3</a>:
The interpreter itself evaluates expressions
using a tree-recursive process.

<p><a name="footnote_Temp_53" href="#call_footnote_Temp_53"><sup><small>33</small></sup></a> For example, work through in detail how the
reduction rule applies to the problem of making change for 10 cents
using pennies and nickels.

<p><a name="footnote_Temp_54" href="#call_footnote_Temp_54"><sup><small>34</small></sup></a> One
approach to coping with redundant computations is to arrange matters
so that we automatically construct a table of values as they
are computed.  Each time we are asked to apply the procedure to some
argument, we first look to see if the value is already stored in the
table, in which case we avoid performing the redundant computation.
This strategy, known as <a name="%_idx_734"></a><a name="%_idx_736"></a><em>tabulation</em> or <em>memoization</em>, can be
implemented in a straightforward way.  Tabulation can sometimes be
used to transform processes that require an exponential number of
steps (such as <tt>count-change</tt>) into processes whose space and time
requirements grow linearly with the input.  See
exercise&nbsp;<a href="book-Z-H-22.html#%_thm_3.27">3.27</a>.

<p><a name="footnote_Temp_57" href="#call_footnote_Temp_57"><sup><small>35</small></sup></a> The elements of Pascal's triangle are called the <em>binomial
coefficients</em>, because the <em>n</em>th row consists of
<a name="%_idx_740"></a>the coefficients of the terms in the
expansion of (<em>x</em> + <em>y</em>)<sup><em>n</em></sup>.  This pattern for computing the coefficients
<a name="%_idx_742"></a>appeared in Blaise Pascal's 1653 seminal work on probability theory, <em>Trait&eacute; du triangle arithm&eacute;tique</em>.  According to
<a name="%_idx_744"></a>Knuth (1973), the same pattern appears in the <em>Szu-yuen
Y&uuml;-chien</em> (``The Precious Mirror of the Four Elements''), published
<a name="%_idx_746"></a><a name="%_idx_748"></a><a name="%_idx_750"></a>by the Chinese mathematician Chu Shih-chieh in 1303, in the
works of the twelfth-century Persian poet and mathematician Omar
Khayyam, and in the works of the twelfth-century Hindu mathematician
Bh&aacute;scara &Aacute;ch&aacute;rya.

<p><a name="footnote_Temp_59" href="#call_footnote_Temp_59"><sup><small>36</small></sup></a> These statements mask a
great deal of oversimplification.  For instance, if we count process
steps as ``machine operations'' we are making the assumption that the
number of machine operations needed to perform, say, a multiplication
is independent of the size of the numbers to be multiplied, which is
false if the numbers are sufficiently large.  Similar remarks hold for
the estimates of space.  Like the design and description of a process,
the analysis of a process can be carried out at various levels of
abstraction.

<p><a name="footnote_Temp_62" href="#call_footnote_Temp_62"><sup><small>37</small></sup></a> More precisely, the number of multiplications
required is equal to 1 less than the log base 2 of <em>n</em> plus the number
of ones in the binary representation of <em>n</em>.  This total is always
less than twice the log base 2 of <em>n</em>.  The arbitrary constants
<em>k</em><sub>1</sub> and <em>k</em><sub>2</sub> in
the definition of order notation imply that, for a logarithmic
process, the base to which logarithms are taken does not matter, so
all such processes are described as <img src="book-Z-G-D-3.gif" border="0">(<tt>log</tt> <em>n</em>).

<p><a name="footnote_Temp_63" href="#call_footnote_Temp_63"><sup><small>38</small></sup></a> You may wonder
why anyone would care about raising numbers to the 1000th power.  See
section&nbsp;<a href="#%_sec_1.2.6">1.2.6</a>.

<p><a name="footnote_Temp_64" href="#call_footnote_Temp_64"><sup><small>39</small></sup></a> This iterative
algorithm is ancient.  It appears in the <em>Chandah-sutra</em> by
<a name="%_idx_810"></a><a name="%_idx_812"></a><a name="%_idx_814"></a>&Aacute;ch&aacute;rya Pingala, written before 200 <font size=-2>B</font>.<font size=-2>C</font>. See Knuth 1981, section
4.6.3, for a full discussion and analysis of this and other methods of
exponentiation.

<p><a name="footnote_Temp_68" href="#call_footnote_Temp_68"><sup><small>40</small></sup></a> This
<a name="%_idx_820"></a><a name="%_idx_822"></a>algorithm, which is sometimes known as the ``Russian peasant method''
of multiplication, is ancient.  Examples of its use are found in the
<a name="%_idx_824"></a>Rhind Papyrus, one of the two oldest mathematical documents in
existence, written about 1700 <font size=-2>B</font>.<font size=-2>C</font>. (and copied from an even
<a name="%_idx_826"></a>older document) by an Egyptian scribe named A'h-mose.

<p><a name="footnote_Temp_70" href="#call_footnote_Temp_70"><sup><small>41</small></sup></a> This exercise was
<a name="%_idx_830"></a><a name="%_idx_832"></a>suggested to us by Joe Stoy, based on an example in Kaldewaij 1990.

<p><a name="footnote_Temp_71" href="#call_footnote_Temp_71"><sup><small>42</small></sup></a> Euclid's Algorithm is so
<a name="%_idx_838"></a>called because it appears in Euclid's <em>Elements</em> (Book 7, ca. 300
<font size=-2>B</font>.<font size=-2>C</font>.).  According to Knuth (1973), it can be considered the
<a name="%_idx_840"></a>oldest known nontrivial algorithm.  The ancient Egyptian method of
multiplication (exercise&nbsp;<a href="#%_thm_1.18">1.18</a>) is surely older,
but, as Knuth explains, Euclid's algorithm is the oldest known to have
been presented as a general algorithm, rather than as a set of
illustrative examples.

<p><a name="footnote_Temp_72" href="#call_footnote_Temp_72"><sup><small>43</small></sup></a> This theorem was proved in 1845 by Gabriel Lam&eacute;, a
<a name="%_idx_850"></a>French mathematician and engineer known chiefly for his contributions
to mathematical physics.  To prove the theorem, we consider pairs
(<em>a</em><sub><em>k</em></sub> ,<em>b</em><sub><em>k</em></sub>), where <em>a</em><sub><em>k</em></sub><u>&gt;</u> <em>b</em><sub><em>k</em></sub>, for which Euclid's Algorithm
terminates in <em>k</em> steps.  The proof is based on the claim that, if
(<em>a</em><sub><em>k</em>+1</sub>, <em>b</em><sub><em>k</em>+1</sub>)  <img src="book-Z-G-D-15.gif" border="0">  (<em>a</em><sub><em>k</em></sub>, <em>b</em><sub><em>k</em></sub>)
 <img src="book-Z-G-D-15.gif" border="0">  (<em>a</em><sub><em>k</em>-1</sub>, <em>b</em><sub><em>k</em>-1</sub>) are three successive pairs in the
reduction process, then we must have <em>b</em><sub><em>k</em>+1</sub><u>&gt;</u> <em>b</em><sub><em>k</em></sub>  +  <em>b</em><sub><em>k</em>-1</sub>.
To verify the claim, consider that a reduction step is defined by
applying the transformation <em>a</em><sub><em>k</em>-1</sub>  =  <em>b</em><sub><em>k</em></sub>, <em>b</em><sub><em>k</em>-1</sub>  = 
 remainder of  <em>a</em><sub><em>k</em></sub> divided by <em>b</em><sub><em>k</em></sub>.  
The second equation means that <em>a</em><sub><em>k</em></sub>  =  <em>q</em><em>b</em><sub><em>k</em></sub>  +  <em>b</em><sub><em>k</em>-1</sub> for some
positive integer <em>q</em>.  And since <em>q</em> must be at least 1 we have <em>a</em><sub><em>k</em></sub>
 =  <em>q</em><em>b</em><sub><em>k</em></sub>  +  <em>b</em><sub><em>k</em>-1</sub> <u>&gt;</u> <em>b</em><sub><em>k</em></sub>  +  <em>b</em><sub><em>k</em>-1</sub>.  But in the previous
reduction step we have <em>b</em><sub><em>k</em>+1</sub> =  <em>a</em><sub><em>k</em></sub>.  Therefore, <em>b</em><sub><em>k</em>+1</sub>  = 
<em>a</em><sub><em>k</em></sub><u>&gt;</u> <em>b</em><sub><em>k</em></sub>  +  <em>b</em><sub><em>k</em>-1</sub>.  This verifies the claim.  Now we can
prove the theorem by induction on <em>k</em>, the number of steps that the
algorithm requires to terminate.  The result is true for <em>k</em> = 1, since
this merely requires that <em>b</em> be at least as large as 
<em>F</em><em>i</em><em>b</em>(1) = 1.  Now, assume that the result is true for all integers less
than or equal to <em>k</em> and establish the result for <em>k</em> + 1.  Let
(<em>a</em><sub><em>k</em>+1</sub>, <em>b</em><sub><em>k</em>+1</sub>) <img src="book-Z-G-D-15.gif" border="0"> (<em>a</em><sub><em>k</em></sub>, <em>b</em><sub><em>k</em></sub>)
 <img src="book-Z-G-D-15.gif" border="0"> (<em>a</em><sub><em>k</em>-1</sub>, <em>b</em><sub><em>k</em>-1</sub>) be successive pairs in the
reduction process.  By our induction hypotheses, we have <em>b</em><sub><em>k</em>-1</sub><u>&gt;</u>
 <em>F</em><em>i</em><em>b</em>(<em>k</em> - 1) and <em>b</em><sub><em>k</em></sub><u>&gt;</u>  <em>F</em><em>i</em><em>b</em>(<em>k</em>).  Thus, applying the claim we just
proved together with the definition of the Fibonacci numbers gives
<em>b</em><sub><em>k</em>+1</sub> <u>&gt;</u> <em>b</em><sub><em>k</em></sub>  +  <em>b</em><sub><em>k</em>-1</sub><u>&gt;</u>  <em>F</em><em>i</em><em>b</em>(<em>k</em>)  +   <em>F</em><em>i</em><em>b</em>(<em>k</em> - 1)  =  <em>F</em><em>i</em><em>b</em>(<em>k</em> + 1), which
completes the proof of Lam&eacute;'s Theorem.

<p><a name="footnote_Temp_75" href="#call_footnote_Temp_75"><sup><small>44</small></sup></a> If <em>d</em> is a divisor of <em>n</em>, then so is <em>n</em>/<em>d</em>.
But <em>d</em> and <em>n</em>/<em>d</em> cannot both be greater than <img src="book-Z-G-D-13.gif" border="0"><em>n</em>.

<p><a name="footnote_Temp_77" href="#call_footnote_Temp_77"><sup><small>45</small></sup></a> Pierre de Fermat (1601-1665) is considered to be the founder of
<a name="%_idx_872"></a><a name="%_idx_874"></a>modern number theory.  He obtained many important number-theoretic
results, but he usually announced just the results, without providing
his proofs.  <a name="%_idx_876"></a>Fermat's Little Theorem was stated in a letter he wrote in
1640.  The first published proof was given by <a name="%_idx_878"></a>Euler in 1736 (and an
<a name="%_idx_880"></a>earlier, identical proof was discovered in the unpublished manuscripts
of Leibniz).  The most famous of Fermat's results -- known as Fermat's
Last Theorem -- was jotted down in 1637 in his copy of the book <em>Arithmetic</em> (by the third-century Greek mathematician <a name="%_idx_882"></a>Diophantus) with the
remark ``I have discovered a truly remarkable proof, but this margin is
too small to contain it.''  Finding a proof of Fermat's Last Theorem
became one of the most famous challenges in number theory.  A complete
<a name="%_idx_884"></a>solution was finally given in 1995 by Andrew Wiles of Princeton University.

<p><a name="footnote_Temp_78" href="#call_footnote_Temp_78"><sup><small>46</small></sup></a> The reduction steps in the cases where the exponent
<em>e</em> is greater than 1 are based on the fact that, for any integers
<em>x</em>, <em>y</em>, and <em>m</em>, we can find the remainder of <em>x</em> times <em>y</em> modulo
<em>m</em> by computing separately the remainders of <em>x</em> modulo <em>m</em> and <em>y</em>
modulo <em>m</em>, multiplying these, and then taking the remainder of the
result modulo <em>m</em>.  For instance, in the case where <em>e</em> is even, we
compute the remainder of <em>b</em><sup><em>e</em>/2</sup> modulo <em>m</em>, square this, and take
the remainder modulo <em>m</em>.  This technique is useful because it means
we can perform our computation without ever having to deal with
numbers much larger than <em>m</em>.  (Compare
exercise&nbsp;<a href="#%_thm_1.25">1.25</a>.)

<p><a name="footnote_Temp_80" href="#call_footnote_Temp_80"><sup><small>47</small></sup></a> Numbers that fool the
<a name="%_idx_912"></a>Fermat test are called <em>Carmichael numbers</em>, and little is known
about them other than that they are extremely rare.  There are 255
Carmichael numbers below 100,000,000.  The smallest few are 561, 1105,
1729, 2465, 2821, and 6601.  In testing primality of very large
numbers chosen at random, the chance of stumbling upon a value that
fools the Fermat test is less than the chance that <a name="%_idx_914"></a>cosmic radiation
will cause the computer to make an error in carrying out a ``correct''
algorithm.  Considering an algorithm to be inadequate for the first
reason but not for the second illustrates the difference between
<a name="%_idx_916"></a><a name="%_idx_918"></a>mathematics and engineering.

<p><a name="footnote_Temp_81" href="#call_footnote_Temp_81"><sup><small>48</small></sup></a> One of the most striking applications of
<a name="%_idx_920"></a>probabilistic prime testing has been to the field of cryptography.
Although it is now computationally infeasible to factor an arbitrary
200-digit number, the primality of such a number can be checked in a
few seconds with the Fermat test.  This fact forms the basis of a
technique for constructing ``unbreakable codes'' suggested by <a name="%_idx_922"></a>Rivest,
<a name="%_idx_924"></a>Shamir, and <a name="%_idx_926"></a>Adleman (1977).  The resulting <a name="%_idx_928"></a><em>RSA algorithm</em> has
become a widely used technique for enhancing the security of
electronic communications.  Because of this and related developments,
the study of <a name="%_idx_930"></a>prime numbers, once considered the epitome of a topic in
``pure'' mathematics to be studied only for its own sake, now turns
out to have important practical applications to cryptography,
electronic funds transfer, and information retrieval.

</div>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-10.html">previous</a></span><span>, <a href="book-Z-H-12.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
